package snippet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.regex.Pattern;

public class Test5 {

	@SuppressWarnings("unused")
	public static void main(String[] args) throws InterruptedException {
		List<Node> children=new ArrayList() {{
			List<Node> c=new ArrayList() {{
				
				add(new Node(5,null));
				add(new Node(6,null));
			}};
			Node n1=new Node(3,c);
			add(n1);
			add(new Node(2,null));
			add(new Node(4,null));
		}};
		Node n =new Node(1, children);
		Test5 t = new Test5();
		//List<Integer> list = t.postorder2(n);
		System.out.println(t.maxDepth(n));
	}
	 public int maxDepth(Node root) {
		 if(root==null) {
			 return 0;
		 }
		 int max=0;
		 if(root.children!=null) {
			 for(Node c:root.children) {
				 max=Math.max(max, maxDepth(c));
			 }
		 }
		 max++;
		return max;  
	    }
    public List<Integer> postorder2(Node root) {
    	List<Integer> list = new ArrayList<>();
    	if(root.children!=null) {
    		for(Node c:root.children) {
    			list.addAll(postorder(c));
    		}
    	}
    	list.add(root.val);
		return list;
        
    }
	
	    public List<Integer> postorder(Node root) {
	    	List<Integer> list = new ArrayList<>();
	    	if(root==null) {
	    		return list;
	    	}
	    	
	    	if(root.children!=null) {
	    		for(Node c:root.children) {
	    			list.addAll(postorder(c));
	    		}
	    	}
	    	list.add(root.val);
			return list;
	        
	    }
	
	 public int peakIndexInMountainArray(int[] A) {
		 	
			for (int i = 1; i < A.length-1; i++) {
				if(A[i-1]<A[i]&&A[i]>A[i+1]) {
					return i;
				}
			}
		
		return 0;
	        
	    }
	 public int findComplement(int num) {
		char[] aa=Integer.toBinaryString(num).toCharArray();
		 for( int i=0;i<aa.length;i++) {
			 if(aa[i]=='1') {
				 aa[i]='0';
			 }else {
				 aa[i]='1';
			 }
		 }
	
		return Integer.parseInt(new String(aa),2);
	        
	    }
	  public TreeNode invertTree(TreeNode root) {
	        if(root!=null) {
	        	TreeNode temp = root.left;
	        	root.left=root.right;
	        	root.right=temp;
	        	invertTree(root.left);
	        	invertTree(root.right);
	        	return root;
	        }else {
	        	return null;
	        }
	    }
	public int maxDepth(TreeNode root) {

		return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

	}

	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
		if (t1 == null && t2 == null)
			return null;
		int t11 = 0, t12 = 0;
		TreeNode l1 = null, l2 = null, r1 = null, r2 = null;
		if (t1 != null) {
			t11 = t1.val;
			l1 = t1.left;
			l2 = t1.right;

		}
		if (t2 != null) {
			t12 = t2.val;
			r1 = t2.left;
			r2 = t2.right;
		}
		TreeNode treeNode = new TreeNode(t11 + t12);

		treeNode.left = mergeTrees(l1, r1);
		treeNode.right = mergeTrees(l2, r2);
		return treeNode;

	}

	public int hammingDistance(int x, int y) {
		System.out.println(Integer.toBinaryString(x ^ y));
		return Integer.bitCount(x ^ y);
	}

	public boolean judgeCircle(String moves) {
		char[] as = moves.toCharArray();
		int a = 0, b = 0;
		for (int i = 0; i < as.length; i++) {
			switch (as[i]) {
			case 'R':
				a++;
				break;
			case 'L':
				a--;
				break;
			case 'U':
				b++;
				break;
			case 'D':
				b--;
				break;

			default:
				break;
			}
		}
		return a == 0 && b == 0;
	}

	public int repeatedNTimes(int[] A) {

		for (int i = 0; i < A.length; i++) {
			for (int j = i + 1; j < A.length; j++) {
				if (A[i] == A[j]) {
					return A[i];
				}
			}
		}
		return 0;

	}

	public int[] sortArrayByParity(int[] A) {
		int[] as = new int[A.length];
		int i = 0, j = 1;
		for (int a : A) {
			if (a % 2 == 0) {
				as[i++] = a;
			} else {
				as[A.length - j++] = a;
			}
		}
		return as;

	}

	public int numUniqueEmails(String[] emails) {
		Set<String> set = new HashSet<>();
		String s1 = "@";
		for (String e : emails) {
			String as[] = e.split(s1);
			set.add(as[0].replaceAll("\\.", "").replaceAll("\\+.*", "") + s1 + as[1]);
		}

		return set.size();

	}

	public int uniqueMorseRepresentations(String[] words) {
		String cs[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
				"-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
		Set<String> s = new HashSet<>();
		for (String w : words) {
			char[] ws = w.toCharArray();
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < ws.length; i++) {
				sb.append(cs[ws[i] - 97]);
			}
			s.add(sb.toString());
		}
		return s.size();

	}

	public int[][] flipAndInvertImage(int[][] A) {
		for (int i = 0; i < A.length; i++) {
			int a[] = A[i];
			int na[] = new int[a.length];
			for (int j = 0; j < a.length; j++) {
				if (a[a.length - j - 1] == 0) {
					na[j] = 1;
				} else {
					na[j] = 0;
				}

			}
			A[i] = na;
		}

		return A;

	}

	public void deleteNode(ListNode node) {
		node.val = node.next.val;
		node.next = node.next.next;
	}

	public int[] diStringMatch(String S) {
		int a = 0, b = S.length();
		int[] as = new int[S.length() + 1];

		for (int i = 0; i < S.length(); i++) {
			if (S.charAt(i) == 'I') {
				as[i] = a++;
			} else {
				as[i] = b--;
			}
		}
		as[S.length()] = b;
		return as;

	}

	public int[] sortedSquares(int[] A) {
		for (int i = 0; i < A.length; i++) {
			A[i] = A[i] * A[i];
		}
		Arrays.sort(A);
		return A;

	}

	public String toLowerCase(String str) {
		char[] cs = str.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			if (cs[i] < 91 && cs[i] > 64) {
				cs[i] = (char) (cs[i] + 32);
			}
		}
		return new String(cs);

	}

	public int numJewelsInStones(String J, String S) {
		int r = 0;
		char[] js = J.toCharArray();
		char[] ss = S.toCharArray();
		for (int i = 0; i < js.length; i++) {
			char a = js[i];
			for (int j = 0; j < ss.length; j++) {
				if (a == ss[j]) {
					r++;
				}
			}
		}
		return r;

	}

	public String longestCommonPrefix(String[] strs) {
		if (strs.length == 0) {
			return "";
		}
		String s = strs[0];
		if (strs.length == 1) {
			return s;
		}

		String reg = "";
		for (int i = 0; i < s.length(); i++) {
			reg = s.substring(0, i + 1);
			for (int j = 1; j < strs.length; j++) {
				if (!Pattern.matches("^" + reg + ".*", strs[j])) {
					return s.substring(0, i);
				}
			}
		}
		return reg;
	}

	/**
	 * 罗马数字转整数
	 * 
	 * @param s
	 * @return
	 */
	public int romanToInt(String s) {
		char[] s1 = s.toCharArray();
		Map<Character, Integer> map = new HashMap() {
			{
				put('I', 1);
				put('V', 5);
				put('X', 10);
				put('L', 50);
				put('C', 100);
				put('D', 500);
				put('M', 1000);
			}
		};
		int re = 0;
		boolean f = true;
		for (int i = s1.length - 1; i >= 0; i--) {
			char c = s1[i];

			if (f) {
				re += map.get(s1[i]);
			} else {
				re -= map.get(s1[i]);
			}
			if (i > 0) {
				char l = s1[i - 1];
				if ((c == 'V' || c == 'X') && l == 'I') {
					f = false;
				} else if ((c == 'L' || c == 'C') && l == 'X') {
					f = false;
				} else if ((c == 'D' || c == 'M') && l == 'C') {
					f = false;
				} else {
					f = true;
				}

			}

		}
		return re;
	}

	// 7整数反转
	public int reverse(int x) {
		long re = 0;
		while (x != 0) {
			re = re * 10 + x % 10;
			if (re > Integer.MAX_VALUE || re < Integer.MIN_VALUE) {
				return 0;
			}
			x = x / 10;
		}
		return (int) re;
	}

	/**
	 * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
	 * 
	 * 示例 1:
	 * 
	 * 输入: 121 输出: true 示例 2:
	 * 
	 * 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3:
	 * 
	 * 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。
	 * 
	 * @param x
	 * @return
	 */
	public boolean isPalindrome(int x) {
		if (x < 0) {
			return false;
		}
		if (x == reverse(x)) {
			return true;
		}
		return false;
	}

	public int[] twoSum(int[] nums, int target) {
		int re[] = new int[2];

		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					re[0] = i;
					re[1] = j;
					break;
				}
			}
		}
		return re;
	}
}



class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
}